package com.fe.class03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Description 双链表实现双端队列，进而实现栈和队列
 * @Author sosuke :-)
 * @Date 2021/12/10 05:52
 */
public class Code04_DoubleEndsQueueToStackAndQueue {

    /**
     * 双链表
     *
     * @param <T>
     */
    public static class Node<T> {
        T data;
        Node<T> last;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 双端队列
     * @param <T>
     */
    public static class DoubleEndsQueue<T> {
        Node<T> head;
        Node<T> tail;

        // 空；不为空
        public void addFromHead(T data) {
            Node<T> cur = new Node<>(data);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }

        // 空；不为空
        public void addFromTail(T data) {
            Node<T> cur = new Node<>(data);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
        }

        // 空；只有一个节点；大于一个节点
        public T popFromHead() {
            if (head == null) {
                return null;
            }
            Node<T> cur = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
                cur.next = null;
            }
            return cur.data;
        }

        // 空；只有一个节点；大于一个节点
        public T popFromTail() {
            if (head == null) {
                return null;
            }
            Node<T> cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.data;
        }

        public boolean isEmpty() {
            return head == null;
        }
    }

    /**
     * 使用双端队列实现栈
     * @param <T>
     */
    public static class MyStack<T> {
        DoubleEndsQueue<T> queue;

        public MyStack() {
            this.queue = new DoubleEndsQueue<>();
        }

        public void push(T data) {
            queue.addFromHead(data);
        }

        public T pop() {
            return queue.popFromHead();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    /**
     * 使用双端队列实现队列
     * @param <T>
     */
    public static class MyQueue<T> {
        DoubleEndsQueue<T> queue;

        public MyQueue() {
            this.queue = new DoubleEndsQueue<>();
        }

        public void push(T data) {
            queue.addFromHead(data);
        }

        public T poll() {
            return queue.popFromTail();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    public static void main(String[] args) {
        int testTimes = 100000;
        int maxValue = 1000;
        int oneTestNums = 100;
        for (int i = 0; i < testTimes; i++) {
            MyStack<Integer> myStack = new MyStack<>();
            MyQueue<Integer> myQueue = new MyQueue<>();
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 0; j < oneTestNums; j++) {
                int numStack = (int) (Math.random() * maxValue);
                if (stack.isEmpty()) {
                    stack.push(numStack);
                    myStack.push(numStack);
                } else {
                    if (Math.random() < 0.5) {
                        stack.push(numStack);
                        myStack.push(numStack);
                    } else {
                        if (!isEqual(stack.pop(), myStack.pop())) {
                            System.out.println("MyStack oops");
                        }
                    }
                }

                int numQueue = (int) (Math.random() * maxValue);
                if (queue.isEmpty()) {
                    queue.offer(numQueue);
                    myQueue.push(numQueue);
                } else {
                    if (Math.random() < 0.5) {
                        queue.offer(numQueue);
                        myQueue.push(numQueue);
                    } else {
                        if (!isEqual(queue.poll(), myQueue.poll())) {
                            System.out.println("MyQueue oops");
                        }
                    }
                }
            }
        }
        System.out.println("Nice");
    }

    private static boolean isEqual(Integer o1, Integer o2) {
        if (null == o1 && null != o2) return false;
        if (null != o1 && null == o2) return false;
        if (null == o1) return true;
        return o1.equals(o2);
    }

}
